package medium;

import java.math.BigDecimal;
import java.util.*;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/11/21 18:26
 */
public class No49_字母的异位词分组 {
    public static void main(String[] args) {
        Solution49 solution49 = new Solution49();
        String[] strs = new String[]{
                "a", "abc", "ab", "ba", "cab"
        };
        List<List<String>> listList = solution49.groupAnagrams(strs);
        System.out.println(listList);
    }
}


class Solution49 {
    public List<List<String>> groupAnagrams(String[] strs) {
        //使用数组计数
        // 'a'-'a' = 0   -> a
        // 'b' -'a' = 1 -> b
        
        //定义map,存放key,value
        //key:形如a1b1c1  value 存放相同组异位词集合
        Map<String,List<String>> map = new HashMap<>();
        List<List<String>> res = new ArrayList<>();

        for (int i = 0; i < strs.length; i++) {
            //每一个维护计数数组
            int[] jishu = new int[26];
            StringBuffer sb = new StringBuffer();
            String data = strs[i];
            //遍历字符串
            for (char c : data.toCharArray()) {
                //数组对应位置++
                jishu[c - 'a']++;
            }
            //遍历数组,该位置不是0,则形成key
            for (int j = 0; j < jishu.length; j++) {
                if (jishu[j] != 0) {
                    //形成key:a1b1c1格式
                    String zimu = ((char) (j + 'a')) + "";
                    sb.append(zimu).append(jishu[j]);
                }
            }
            
            //现在sb是key
            if (map.get(sb.toString()) == null) {
                map.put(sb.toString(), new ArrayList<>());
            }
            map.get(sb.toString()).add(strs[i]);
        }
        return new ArrayList<>(map.values());
    }
}



    //public List<List<String>> groupAnagrams(String[] strs) {
    //    //通过将字符串排序确定异位词
    //    
    //    //indexMap:存放种类样例排序和编号,故同一编号必然是异位词搞来的
    //    Map<String,Integer> indexMap = new HashMap<>();
    //    //编号,也可以作list索引
    //    List<List<String>> res = new ArrayList<>();
    //    int index = -1;
    //    //遍历数组
    //    for (int i = 0; i < strs.length; i++) {
    //        String data = strs[i];
    //        data = getSortString(data);
    //        
    //        //如果排序在indexMap没有,编号+1
    //        if (indexMap.get(data) == null) {
    //            index++;
    //            //存入indexMap
    //            indexMap.put(data, index);//a->0 abc->1 bc->2
    //            //res加新元素
    //            List<String> dataList = new ArrayList<>();
    //            dataList.add(strs[i]);
    //            res.add(dataList);
    //        } else {
    //            //有,说明数组这个元素是索引=indexMap对应data值的位置的异位词
    //            int dataIndex = indexMap.get(data);
    //            res.get(dataIndex).add(strs[i]);
    //        } 
    //    }
    //    return res;
    //}
    //
    ////将字符串排序
    //public String getSortString(String data) {
    //    char[] chars = data.toCharArray();
    //    Arrays.sort(chars);
    //    String base = "";
    //    for (char c : chars) {
    //        base += c;
    //    }
    //    return base;
    //}



    //public List<List<String>> groupAnagrams(String[] strs) {
    //    // abcd -> dbca
    //    // map  ddbbcc -> d2 b2 c2  ddbbbb - d2 b4 x
    //    // map ddbbcc -> ddbbcc ??????? 坑!!!!!
    //    
    //    // a->a 也是!!!!
    //    
    //    //万物???  暴力法!!!
    //    //用于种类样例检查其他种类
    //    Map<Character, Integer> checkMap = new HashMap<>();
    //    //结果
    //    List<List<String>> res = new ArrayList<>();
    //    for (int red = 0; red < strs.length; red++) {
    //        //对于每一个map,为防止不同种类冲突,需要清空
    //        checkMap.clear();
    //        if (!"-6666".equals(strs[red])) {
    //            //红指针指向不同类,所以,分组
    //            List<String> data = new ArrayList<>();
    //            //种类样例扔入
    //            data.add(strs[red]);
    //            //map生成
    //            getMap(checkMap, strs[red]);
    //            //checkMap: a1 b1 c1
    //            //遍历标记
    //            strs[red] = "-6666";
    //
    //            //处理绿指针
    //            out:for (int green = 0; green < strs.length; green++) {
    //                if (!"-6666".equals(strs[green])) {
    //                    //遍历
    //                    //值传递,注意,由于可能有多个异位词,导致checkMap只能允许修改1次
    //                    //因此,复制出来搞
    //                    Map<Character, Integer> checkMapCopy = new HashMap<>(checkMap);
    //                    
    //                    for (char c : strs[green].toCharArray()) {
    //                        // bca,aa,x    // ab
    //                        //map a1 b1 c1
    //                        if (checkMap.get(c) == null) {
    //                            continue out;
    //                        }
    //                        //有的话,值减1
    //                        checkMapCopy.put(c, checkMapCopy.get(c) - 1);
    //                        //aa
    //
    //                        //再判断
    //                        if (checkMapCopy.get(c) < 0) {
    //                            continue out;
    //                        }
    //                    }
    //
    //                    //map查询全部是0才加入
    //                    //遍历map
    //                    for (Map.Entry<Character, Integer> map : checkMapCopy.entrySet()) {
    //                        if (map.getValue() > 0) {
    //                            continue out;
    //                        }
    //                    }
    //
    //                    data.add(strs[green]);
    //                    //标记
    //                    strs[green] = "-6666";
    //                }
    //            }
    //            //绿指针找完同类,扔入
    //            res.add(data);
    //        }
    //    }
    //    return res;
    //}
    //
    //
    ////将字符串转map
    //public void getMap(Map<Character, Integer> map, String str) {
    //    for (char c : str.toCharArray()) {
    //        if (map.get(c) == null) {
    //            map.put(c, 1);
    //        } else {
    //            map.put(c, map.get(c) + 1);
    //        } 
    //    }
    //}


